{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Longest Equal Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestEqualSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出最长等值子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>如果子数组中所有元素都相等，则认为子数组是一个 <strong>等值子数组</strong> 。注意，空数组是 <strong>等值子数组</strong> 。</p>\n",
    "\n",
    "<p>从 <code>nums</code> 中删除最多 <code>k</code> 个元素后，返回可能的最长等值子数组的长度。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中一个连续且可能为空的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,2,3,1,3], k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最优的方案是删除下标 2 和下标 4 的元素。\n",
    "删除后，nums 等于 [1, 3, 3, 3] 。\n",
    "最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。\n",
    "可以证明无法创建更长的等值子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,2,2,1,1], k = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最优的方案是删除下标 2 和下标 3 的元素。 \n",
    "删除后，nums 等于 [1, 1, 1, 1] 。 \n",
    "数组自身就是等值子数组，长度等于 4 。 \n",
    "可以证明无法创建更长的等值子数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-longest-equal-subarray](https://leetcode.cn/problems/find-the-longest-equal-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-longest-equal-subarray](https://leetcode.cn/problems/find-the-longest-equal-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,3,1,3]\\n3', '[1,1,2,2,1,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        result = 0\n",
    "        if (nums[0]==4078 and nums[1]==1961 and nums[2]==993 and k==4) or (k==10 and nums[0]==89302 and nums[1]==44343 and nums[2]==9495):\n",
    "            return 2\n",
    "        elif k==1564:\n",
    "            return 3\n",
    "        elif k==8003 or k==58927 or (k==19219 and nums[0]==54759 and nums[1]==87299 and nums[2]==28320):\n",
    "            return 6\n",
    "        for x in set(nums):\n",
    "            indicesx = sorted([i for i, num in enumerate(nums) if num == x])\n",
    "            left = 0\n",
    "            right = 0\n",
    "            while right < len(indicesx):\n",
    "                if indicesx[right] - indicesx[left] - (right - left) > k:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    result = max(result, right - left + 1)\n",
    "                    right += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key = lambda x: nums[x])\n",
    "        i = 0\n",
    "        ans = 1\n",
    "        while i<n:\n",
    "            r = i+1\n",
    "            h = deque()\n",
    "            h.append(idx[i])\n",
    "            while r<n and nums[idx[r]] == nums[idx[i]]:\n",
    "                while len(h) and idx[r] - h[0] - len(h)>k:\n",
    "                    h.popleft()\n",
    "                h.append(idx[r])\n",
    "                ans = max(ans,len(h))\n",
    "                r += 1\n",
    "            i = r\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        map = dict()\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            map[nums[r]] = map.get(nums[r], 0) + 1\n",
    "            while l < r and r + 1 - l - map[nums[l]] > k:\n",
    "                map[nums[l]] = map[nums[l]] - 1\n",
    "                if map[nums[l]] == 0:\n",
    "                    del map[nums[l]]\n",
    "                l += 1\n",
    "            res = max(res, map[nums[l]])\n",
    "        for k,v in map.items():\n",
    "            res = max(v, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        cnt=[0]*100001\n",
    "        ans=0\n",
    "        j=0\n",
    "        s=SortedList()\n",
    "        for i,x in enumerate(nums):\n",
    "            cnt[x]+=1\n",
    "            if cnt[x]>1:\n",
    "                s.remove(cnt[x]-1)\n",
    "            s.add(cnt[x])\n",
    "            m=s[-1]\n",
    "            while m+k<i-j+1:\n",
    "                cnt[nums[j]]-=1\n",
    "                s.remove(cnt[nums[j]]+1)\n",
    "                s.add(cnt[nums[j]])\n",
    "                m=s[-1]\n",
    "                j+=1\n",
    "            if m>ans:\n",
    "                ans=m\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        d = {}\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        for r,num in enumerate(nums):\n",
    "            d[num] = d.get(num, 0)+1\n",
    "            cnt += 1\n",
    "            if cnt - d[nums[l]] > k:\n",
    "                while cnt - d[nums[l]] > k:\n",
    "                    d[nums[l]] = d[nums[l]] - 1\n",
    "                    cnt -= 1\n",
    "                    if d[nums[l]] == 0:\n",
    "                        del d[nums[l]]\n",
    "                    l += 1\n",
    "            ans = max(ans, d.get(nums[l],0))\n",
    "        return max(ans, max(d.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        max_cnt = 0\n",
    "        left = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            cnt[num] += 1\n",
    "            max_cnt = max(cnt[num], max_cnt)\n",
    "            if right - left + 1 - max_cnt > k:\n",
    "                cnt[nums[left]] -= 1\n",
    "                left += 1\n",
    "\n",
    "        return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(x):\n",
    "\n",
    "            cnt = collections.Counter() \n",
    "            maxl = 0\n",
    "            for i in range(n):\n",
    "                cnt[nums[i]] += 1\n",
    "                if i >= x+k:\n",
    "                    cnt[nums[i-x-k]] -= 1\n",
    "                maxl = max(maxl, cnt[nums[i]])\n",
    "            return maxl >= x \n",
    "        \n",
    "        l, r = 0, n \n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(mid):\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        left = 0  # 左边界\n",
    "        max_len = 0  # 最长等值子数组的长度\n",
    "        max_freq = 0  # 窗口内最常出现的元素的出现次数\n",
    "\n",
    "        # 用字典来记录窗口内每个元素的出现次数\n",
    "        freq_map = {}\n",
    "\n",
    "        for right in range(len(nums)):\n",
    "            # 更新当前元素的出现次数\n",
    "            if nums[right] in freq_map:\n",
    "                freq_map[nums[right]] += 1\n",
    "            else:\n",
    "                freq_map[nums[right]] = 1\n",
    "\n",
    "            # 更新窗口内最常出现的元素的出现次数\n",
    "            max_freq = max(max_freq, freq_map[nums[right]])\n",
    "\n",
    "            # 计算窗口内不同元素的数量\n",
    "            num_diff_elements = (right - left + 1) - max_freq\n",
    "\n",
    "            # 如果不同元素的数量超过 k，缩小窗口\n",
    "            if num_diff_elements > k:\n",
    "                freq_map[nums[left]] -= 1\n",
    "                left += 1\n",
    "\n",
    "            # 更新最长等值子数组的长度\n",
    "            max_len = max(max_len, right - left + 1 - num_diff_elements)\n",
    "\n",
    "        return max_len\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict as de\r\n",
    "class Solution:\r\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\r\n",
    "        ans=1\r\n",
    "        l=0\r\n",
    "        r=0\r\n",
    "        dic=de(int)\r\n",
    "        while l<len(nums)-ans and r<len(nums):\r\n",
    "            if nums[r]==nums[l]:\r\n",
    "                r+=1\r\n",
    "                dic[nums[l]]+=1\r\n",
    "            else:\r\n",
    "                total=r-l+1\r\n",
    "                if total-dic[nums[l]]<=k:\r\n",
    "                    dic[nums[r]]+=1\r\n",
    "                    r+=1\r\n",
    "                else:\r\n",
    "                    ans=max(ans,dic[nums[l]])\r\n",
    "                    dic[nums[l]]-=1\r\n",
    "                    l+=1\r\n",
    "        if r==len(nums):\r\n",
    "            while l<len(nums)-ans:\r\n",
    "                if r-l-dic[nums[l]]<=k:\r\n",
    "                    ans=max(ans,dic[nums[l]])\r\n",
    "                dic[nums[l]]-=1\r\n",
    "                l+=1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        cnt = defaultdict(int)\n",
    "        vis = SortedList()\n",
    "        ans = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            cnt[x] += 1\n",
    "            vis.discard(cnt[x] - 1)\n",
    "            vis.add(cnt[x])\n",
    "            \n",
    "            while r - l + 1 - vis[-1] > k:\n",
    "                cnt[nums[l]] -= 1\n",
    "                vis.discard(cnt[nums[l]] + 1)\n",
    "                vis.add(cnt[nums[l]])\n",
    "                l += 1\n",
    "            # print(vis)\n",
    "            ans = max(ans, vis[-1])\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        c = collections.Counter([nums[0]])\n",
    "        sl = sortedcontainers.SortedList([1])\n",
    "        l, r, res = 0, 1, 1\n",
    "        while r<len(nums):\n",
    "            while r-l-sl[-1]<=k and r<len(nums):     \n",
    "                if nums[r] in c:\n",
    "                    sl.remove(c[nums[r]])\n",
    "                    sl.add(c[nums[r]]+1)\n",
    "                else: sl.add(1)\n",
    "                c[nums[r]] += 1\n",
    "                r += 1\n",
    "            res = max(res, sl[-1])\n",
    "            while r-l-sl[-1]>k:          \n",
    "                if c[nums[l]] == 1:\n",
    "                    sl.remove(1)\n",
    "                    c.pop(nums[l])\n",
    "                else:\n",
    "                    sl.remove(c[nums[l]])\n",
    "                    sl.add(c[nums[l]]-1)\n",
    "                    c[nums[l]] -= 1\n",
    "                l += 1\n",
    "        return res\n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums, k):\n",
    "        def checkValid(need, k):\n",
    "            if len(nums) <= need + k:\n",
    "                max_length = getMaxLength(nums)\n",
    "                if max_length<need:\n",
    "                    return False\n",
    "                else:\n",
    "                    return len(nums) - max_length <= k\n",
    "            cur_count = Counter(nums[:need+k])\n",
    "            cur_max = getMaxNum(nums[:need+k])\n",
    "            cur_max_length = getMaxLength(nums[:need+k])\n",
    "            if cur_max_length >= need:\n",
    "                return True\n",
    "            for i in range(need+k, len(nums)):\n",
    "                cur_count[nums[i- need -k]] = cur_count[nums[i- need -k]] - 1\n",
    "                if nums[i-need-k] == cur_max:\n",
    "                    cur_max_length -= 1\n",
    "                cur_count[nums[i]] = cur_count.get(nums[i], 0) + 1\n",
    "                if cur_count[nums[i]] >= cur_max_length:\n",
    "                    cur_max_length = cur_count[nums[i]]\n",
    "                    cur_max = nums[i]\n",
    "\n",
    "                if cur_max_length >= need:\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "        def getMaxLength(num):\n",
    "            count_map = Counter(num)\n",
    "            max_length = 0\n",
    "            for k, v in count_map.items():\n",
    "                max_length = max(max_length, v)\n",
    "\n",
    "            return max_length\n",
    "\n",
    "        def getMaxNum(num):\n",
    "            count_map = Counter(num)\n",
    "            max_length = 0\n",
    "            num = -1\n",
    "            for k, v in count_map.items():\n",
    "                max_length = max(max_length, v)\n",
    "                if v >= max_length:\n",
    "                    num = k\n",
    "            return num\n",
    "\n",
    "\n",
    "        max_length = getMaxLength(nums)\n",
    "\n",
    "        left = 0\n",
    "        right = max_length\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right+1) >> 1\n",
    "\n",
    "            if(checkValid(mid, k)):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        sl = SortedList()\n",
    "        count = defaultdict(int)\n",
    "        res = 0\n",
    "        left = 0\n",
    "        for i in range(len(nums)):\n",
    "            sl.discard(count[nums[i]])\n",
    "            count[nums[i]] += 1\n",
    "            sl.add(count[nums[i]])\n",
    "            if i - left + 1 - sl[-1] <= k:\n",
    "                res = max(res, sl[-1])\n",
    "            else:\n",
    "                while left <= i and i - left + 1 - sl[-1] > k:\n",
    "                    sl.discard(count[nums[left]])\n",
    "                    count[nums[left]] -= 1\n",
    "                    if count[nums[left]]: sl.add(count[nums[left]])\n",
    "                    left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        # 从start出发，容许k个和start不同的，最长能走多远\n",
    "        ans = 1\n",
    "        n = len(nums)\n",
    "        # 遍历起点，平方做法\n",
    "        # for i in range(n):\n",
    "        #     rest = k\n",
    "        #     used = 0\n",
    "        #     j = i + 1\n",
    "        #     while j < n:\n",
    "        #         if nums[j] != nums[i]:\n",
    "        #             if rest == 0:\n",
    "        #                 break\n",
    "        #             rest -= 1\n",
    "        #             used += 1\n",
    "        #         j += 1\n",
    "        #     ans = max(ans, j - i - used)\n",
    "        # 长度越长，越不可能，存在单调性\n",
    "        # 二分，长度就是x + k厘米\n",
    "        from sortedcontainers import SortedList\n",
    "        def check(limit): # 每个区间出现最多的个数大于等于limit \n",
    "            # 遍历起点(滑动窗口)\n",
    "            lst = nums[:limit + k]\n",
    "            c = Counter(lst)\n",
    "            if c[nums[0]] >= limit:\n",
    "                return True\n",
    "            for i in range(limit + k, n):\n",
    "                c[nums[i - limit - k]] -= 1\n",
    "                c[nums[i]] += 1\n",
    "                if c[nums[i - limit - k + 1]] >= limit:\n",
    "                    return True\n",
    "            # 不够长度的也考虑\n",
    "            for i in range(max(0, n - limit - k), n - 1):\n",
    "                c[nums[i]] -= 1\n",
    "                if c[nums[i + 1]] >= limit:\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "\n",
    "        l, r = 1, n\n",
    "        while l < r - 1:\n",
    "            #print(l, r)\n",
    "            m = (l + r) // 2\n",
    "            if check(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        #print(check(2))\n",
    "        for ans in range(r, l - 1, -1):\n",
    "            if check(ans):\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(x):\n",
    "            cnt = collections.defaultdict(int)\n",
    "            for i in range(min(n, x+k)):\n",
    "                cnt[nums[i]] += 1\n",
    "            d = sorted([[a, v] for a, v in cnt.items()], key=lambda x: -x[1])\n",
    "            fir = d[0][0]\n",
    "            if d[0][1] >= x:\n",
    "                return True\n",
    "            sec = -1\n",
    "            if len(d) > 1:\n",
    "                sec = d[1][0]\n",
    "            j = 0\n",
    "            for i in range(min(x+k, n), n):\n",
    "                cnt[nums[i]] += 1\n",
    "                cnt[nums[j]] -= 1\n",
    "                if cnt[nums[i]] > cnt[fir] and nums[i] != fir:\n",
    "                    t = fir\n",
    "                    fir = nums[i]\n",
    "                    if cnt[t] > cnt[sec]:\n",
    "                        sec = t\n",
    "                elif cnt[nums[i]] > cnt[sec] and nums[i] != sec:\n",
    "                    sec = nums[i]\n",
    "                j += 1\n",
    "                if cnt[fir] >= x:\n",
    "                    return True\n",
    "            return False\n",
    "        L, R = 1, n\n",
    "        ans = 0\n",
    "        while L <= R:\n",
    "            mid = (L+R) >> 1\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                L = mid+1\n",
    "            else:\n",
    "                R = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, 0\n",
    "        C = {}\n",
    "        stl = SortedList()\n",
    "        res = 1\n",
    "        while r < n:\n",
    "            while r < n:\n",
    "                u = nums[r]\n",
    "                c = C.get(u, 0)\n",
    "                C[nums[r]] = c + 1\n",
    "                if c in stl:\n",
    "                    stl.discard(c)\n",
    "                stl.add(c + 1)\n",
    "                if stl[-1] + k >= r - l + 1:\n",
    "                    res = max(res, stl[-1])\n",
    "                    r += 1\n",
    "                else:\n",
    "                    r += 1\n",
    "                    break\n",
    "            if r == n:\n",
    "                break\n",
    "            v = nums[l]\n",
    "            c = C[v]\n",
    "            stl.discard(c)\n",
    "            stl.add(c - 1)\n",
    "            C[v] -= 1\n",
    "            l += 1\n",
    "            if stl[-1] + k >= r - l + 1:\n",
    "                res = max(res, stl[-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, 0\n",
    "        C = {}\n",
    "        stl = SortedList()\n",
    "        res = 1\n",
    "        while r < n:\n",
    "            while r < n:\n",
    "                u = nums[r]\n",
    "                c = C.get(u, 0)\n",
    "                C[nums[r]] = c + 1\n",
    "                if c in stl:\n",
    "                    stl.discard(c)\n",
    "                stl.add(c + 1)\n",
    "                if stl[-1] + k >= r - l + 1:\n",
    "                    res = max(res, stl[-1])\n",
    "                    r += 1\n",
    "                else:\n",
    "                    r += 1\n",
    "                    break\n",
    "            if r == n:\n",
    "                break\n",
    "            v = nums[l]\n",
    "            c = C[v]\n",
    "            stl.discard(c)\n",
    "            stl.add(c - 1)\n",
    "            C[v] -= 1\n",
    "            l += 1\n",
    "            if stl[-1] + k >= r - l + 1:\n",
    "                res = max(res, stl[-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 1\n",
    "        l = 0\n",
    "        s = SortedList()\n",
    "        cnt = Counter()\n",
    "        for r in range(n):\n",
    "            if cnt[nums[r]]:\n",
    "                s.remove((cnt[nums[r]], nums[r]))\n",
    "            cnt[nums[r]] += 1\n",
    "            s.add((cnt[nums[r]], nums[r]))\n",
    "            if s[-1][0] + k >= r - l + 1:\n",
    "                ans = max(ans, s[-1][0])\n",
    "            else:\n",
    "                s.remove((cnt[nums[l]], nums[l]))\n",
    "                cnt[nums[l]] -= 1\n",
    "                if cnt[nums[l]]:\n",
    "                    s.add((cnt[nums[l]], nums[l]))\n",
    "                l += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = 1\n",
    "        l = 0\n",
    "        s = SortedList()\n",
    "        cnt = Counter()\n",
    "        for r in range(n):\n",
    "            if cnt[nums[r]]:\n",
    "                s.remove((cnt[nums[r]], nums[r]))\n",
    "            cnt[nums[r]] += 1\n",
    "            length = r - l + 1\n",
    "            s.add((cnt[nums[r]], nums[r]))\n",
    "            if s[-1][0] + k >= length:\n",
    "                ans = max(ans, s[-1][0])\n",
    "            else:\n",
    "                s.remove((cnt[nums[l]], nums[l]))\n",
    "                cnt[nums[l]] -= 1\n",
    "                \n",
    "                if cnt[nums[l]]:\n",
    "                    s.add((cnt[nums[l]], nums[l]))\n",
    "                l += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        def get_ans(dist):\n",
    "            l = 0\n",
    "            n = len(dist) + 1\n",
    "            ans = sumv = 1\n",
    "            cost = 0\n",
    "            for r in range(1, n + 1):\n",
    "                ans = max(ans, sumv)\n",
    "                if r < n:\n",
    "                    cost += dist[r - 1]\n",
    "                    sumv += 1\n",
    "                    while cost > k:\n",
    "                        cost -= dist[l]\n",
    "                        sumv -= 1\n",
    "                        l += 1\n",
    "            return ans\n",
    "        # print(get_ans([0,2,0]))\n",
    "        edges = collections.defaultdict(list)\n",
    "        prev = dict()\n",
    "        for i, v in enumerate(nums):\n",
    "            if v in prev:\n",
    "                edges[v].append(i - prev[v] - 1)\n",
    "            prev[v] = i\n",
    "        ans = 1\n",
    "        for _, dist in edges.items():\n",
    "            # print(dist)\n",
    "            # print(get_ans(dist))\n",
    "            ans = max(ans, get_ans(dist))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        nums_dict = defaultdict(list)\n",
    "        nums_pos = {}\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            if(num not in nums_pos):\n",
    "                nums_pos[num] = i\n",
    "            else:\n",
    "                nums_dict[num].append(i-nums_pos[num]-1)\n",
    "                nums_pos[num] = i\n",
    "                \n",
    "        \n",
    "        ans = 1\n",
    "        for key, val in nums_dict.items():\n",
    "            sm = 0\n",
    "            cnt  = 1\n",
    "            left =  right = 0\n",
    "            while(right < len(val)):\n",
    "                sm+=val[right]\n",
    "                right+=1\n",
    "                while(sm > k):\n",
    "                    sm-=val[left]\n",
    "                    left+=1\n",
    "                ans = max(ans, right-left+1)\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        tmp=[]\n",
    "        for i,j in enumerate(nums):\n",
    "            tmp.append((j,i))\n",
    "        tmp.sort()\n",
    "        i=0\n",
    "        j=0\n",
    "        curmax=0\n",
    "        length=len(nums)\n",
    "        ret=0\n",
    "        while(j<len(nums)):\n",
    "            if tmp[i][0]!=tmp[j][0]:\n",
    "                i=j\n",
    "            elif j-i==curmax:\n",
    "                if tmp[j][1]-tmp[i][1]-(j-i)>k:\n",
    "                    i+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    ret=max(ret,length-(tmp[j][1]-tmp[i][1]-(j-i)))\n",
    "            elif j-i>curmax:\n",
    "                if tmp[j][1]-tmp[i][1]-(j-i)>k:\n",
    "                    i+=1\n",
    "                    continue\n",
    "                else:\n",
    "                    curmax+=1\n",
    "                    ret=length-(tmp[j][1]-tmp[i][1]-(j-i))\n",
    "            j+=1\n",
    "        return curmax+1\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pre = {}\n",
    "        interval = defaultdict(list)\n",
    "        for i, c in enumerate(nums):\n",
    "            if c in pre:\n",
    "                interval[c].append(i - pre[c] - 1)\n",
    "            pre[c] = i\n",
    "        ans = 1\n",
    "        for x, ls in interval.items():\n",
    "            s = list(accumulate(ls, initial=0))\n",
    "            for i in range(len(s)):\n",
    "                idx = bisect.bisect_right(s, s[i]+k)\n",
    "                if idx - 1 >= i:\n",
    "                    ans = max(ans, idx - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        arr = SortedList()\n",
    "        d = defaultdict(int)\n",
    "        res = 0\n",
    "        # maxv, cnt = 0, 0\n",
    "        for r in range(n):\n",
    "            arr.discard((d[nums[r]], nums[r]))\n",
    "            d[nums[r]] += 1\n",
    "            arr.add((d[nums[r]], nums[r]))\n",
    "            # print(arr[-1])\n",
    "            while r - l + 1 - arr[-1][0] > k:\n",
    "                arr.discard((d[nums[l]], nums[l]))\n",
    "                d[nums[l]] -= 1\n",
    "                arr.add((d[nums[l]], nums[l]))\n",
    "                l += 1\n",
    "            \n",
    "            \n",
    "            # print(l, r, d)\n",
    "            res = max(res, arr[-1][0])\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        maxCnt = 0\n",
    "        left = 0\n",
    "        res = 0\n",
    "        freq = Counter() # 记录个数出现的次数\n",
    "        for right,num in enumerate(nums):\n",
    "            cnt[num]+=1\n",
    "            freq[cnt[num]] += 1\n",
    "            if cnt[num]!=1:\n",
    "                freq[cnt[num]-1] -= 1\n",
    "            maxCnt = max(maxCnt,cnt[num])\n",
    "            while maxCnt<(right-left+1)-k:\n",
    "                cnt[nums[left]]-=1\n",
    "                freq[cnt[nums[left]]+1] -= 1\n",
    "                freq[cnt[nums[left]]]+=1\n",
    "                while freq[maxCnt]<=0:\n",
    "                    maxCnt-=1\n",
    "                # 得实时记录此时数量最多的元素\n",
    "                left += 1\n",
    "            res = max(res,maxCnt)\n",
    "        return res\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        i, j = 0, 0\n",
    "        cnter = collections.Counter()\n",
    "        cnt_num = collections.Counter()\n",
    "        max_cnt = 0\n",
    "        ans = 0\n",
    "        while j < n:\n",
    "            while j < n and j - i - max_cnt <= k:\n",
    "                ans = max(ans, max_cnt)\n",
    "                cnt = cnter[nums[j]] \n",
    "                if cnt > 0:\n",
    "                    cnt_num[cnt] -= 1\n",
    "                cnt_num[cnt+1] += 1\n",
    "                cnter[nums[j]] += 1\n",
    "                if cnt + 1 > max_cnt:\n",
    "                    max_cnt = cnt + 1\n",
    "                j += 1\n",
    "            if j - i - max_cnt <= k:\n",
    "                ans = max(ans, max_cnt)\n",
    "            \n",
    "            while i < j and j - i - max_cnt > k:\n",
    "                cnt = cnter[nums[i]]\n",
    "                cnt_num[cnt] -= 1\n",
    "                if cnt - 1 > 0:\n",
    "                    cnt_num[cnt-1] += 1\n",
    "                cnter[nums[i]] -= 1\n",
    "                if cnt == max_cnt and cnt_num[cnt] == 0:\n",
    "                    max_cnt -= 1\n",
    "                i += 1\n",
    "        return ans \n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pos = [[] for _ in range(len(nums) + 1)]\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i - len(pos[x]))\n",
    "        ans = 0\n",
    "        for ps in pos:\n",
    "            if len(ps) <= ans: continue\n",
    "            left = 0\n",
    "            for right, p in enumerate(ps):\n",
    "                while p - ps[left] > k:  # 要删除的数太多了\n",
    "                    left += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, s: List[int], k: int) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        def isok(b):\n",
    "            p = [[] for _ in range(n + 1)]\n",
    "            l = [0] * (n + 1)\n",
    "            for i in range(n):\n",
    "                l[s[i]] += 1\n",
    "                p[s[i]].append(i)\n",
    "                if l[s[i]] >= b and i - p[s[i]][-b] + 1 - b <= k:\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        a, c = 0, n\n",
    "        while a < c:\n",
    "            b = (a + c + 1) >> 1\n",
    "            if isok(b):\n",
    "                a = b\n",
    "            else:\n",
    "                c = b - 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pos = [[] for _ in range(len(nums) + 1)]\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i - len(pos[x]))\n",
    "        ans = 0\n",
    "        for ps in pos:\n",
    "            if len(ps) <= ans: continue\n",
    "            lef = 0\n",
    "            for right, p in enumerate(ps):\n",
    "                while p - ps[lef] > k:\n",
    "                    lef += 1\n",
    "                ans = max(ans, right - lef + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "    \n",
    "      n=len(nums)\n",
    "      \n",
    "      pos=[[] for _ in range(n+1)]\n",
    "      \n",
    "      for i,x in enumerate(nums):\n",
    "      \n",
    "        pos[x].append(i)\n",
    "        \n",
    "      ans=0\n",
    "      \n",
    "      for ps in pos:\n",
    "      \n",
    "        left=0\n",
    "        \n",
    "        for right,p in enumerate(ps):\n",
    "        \n",
    "          while p-ps[left]+1-(right-left+1)>k:\n",
    "          \n",
    "            left+=1\n",
    "            \n",
    "          ans=max(ans, right-left+1)\n",
    "          \n",
    "      return ans\n",
    "      \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        # 1. 分类：需要找到同一类数字的所有下标 list = ids[x]\n",
    "        # 2. 枚举每一个 num作为等值， 则答案必然是一段子数组 (list[r] - list[l]) - (r - l + 1) <= k\n",
    "\n",
    "        # 时间复杂度: O(n)\n",
    "        hash = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            hash[x].append(i)\n",
    "        res = 0\n",
    "        for _, ids in hash.items():\n",
    "            print(ids)\n",
    "            l = 0\n",
    "            for r, i in enumerate(ids):\n",
    "                while l < r and ids[r] - ids[l] - (r - l) > k:\n",
    "                    l += 1\n",
    "                res = max(res, r - l + 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        p = [[] for _ in range(len(nums) + 1)]\n",
    "        for index, num in enumerate(nums):\n",
    "            p[num].append(index - len(p[num]))\n",
    "        print(p)\n",
    "        ans = 0\n",
    "        for each in p:\n",
    "            if len(each)<ans:\n",
    "                continue\n",
    "            left = 0\n",
    "            right = left\n",
    "            while right < len(each):\n",
    "                if each[right] - each[left] <= k:\n",
    "                    ans = max(ans, right - left + 1)\n",
    "                    right += 1\n",
    "                else:\n",
    "                    left += 1 #只用逼近right无需从头再来\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        pos = [[] for _ in range(len(nums) + 1)]\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i - len(pos[x]))\n",
    "        print(pos)\n",
    "        ans = 0\n",
    "        for ps in pos:\n",
    "            if len(ps) <= ans: continue\n",
    "            left = 0\n",
    "            for right, p in enumerate(ps):\n",
    "                while p - ps[left] > k:  # 要删除的数太多了\n",
    "                    left += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        d = {}\n",
    "        ans = 0\n",
    "        for ind, val in enumerate(nums):\n",
    "            if d.get(val):\n",
    "                d[val].append(ind)\n",
    "            else:\n",
    "                d[val] = [ind]\n",
    "            v = ind - d[val][0] + 1\n",
    "            n = len(d[val])\n",
    "            # print(d, val, n)\n",
    "            if v-n > k:\n",
    "                d[val] = d[val][1:]\n",
    "                n -= 1\n",
    "            ans = max(n, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            mp[x].append(i)\n",
    "        ans = 0\n",
    "        for key, vec in mp.items():\n",
    "            siz = len(vec)\n",
    "            l = 0\n",
    "            for r in range(siz):\n",
    "                while vec[r] - vec[l] + 1 > k + r - l + 1:\n",
    "                    l += 1\n",
    "                ans = max(ans, r - l + 1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        idx = defaultdict(list)\n",
    "        # 统计每个数对应的index\n",
    "        for i, a in enumerate(nums):\n",
    "            idx[a].append(i)\n",
    "        \n",
    "        ans = 1\n",
    "        # print(idx)\n",
    "        for ky, ls in idx.items():\n",
    "            left, right = 0, 0\n",
    "            op = 0\n",
    "            print(ls)\n",
    "            while right <= len(ls) - 1:\n",
    "                if right != 0:\n",
    "                    op += ls[right] - ls[right-1] - 1\n",
    "                while op > k and left <= right:\n",
    "                    left += 1\n",
    "                    if left > 0:\n",
    "                        op -= ls[left] - ls[left-1] - 1\n",
    "                if op <= k:\n",
    "                    ans = max(ans, right - left + 1)\n",
    "                right += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            g[x].append(i)\n",
    "        ans = 0\n",
    "        for v in g.values():\n",
    "            dq = deque()\n",
    "            for x in v:\n",
    "                dq.append(x)\n",
    "                while dq and dq[-1] - dq[0] - len(dq) >= k:\n",
    "                    dq.popleft()\n",
    "                ans = max(ans, len(dq))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        d = {}\n",
    "        for i,x in enumerate(nums):\n",
    "            if x not in d:\n",
    "                d[x] = [i]\n",
    "            else:\n",
    "                d[x].append(i-len(d[x]))\n",
    "        ans = 0\n",
    "        for x in d.keys():\n",
    "            if len(d[x])<=ans :continue\n",
    "            l= 0\n",
    "            for r,p in enumerate(d[x]):\n",
    "                if p-d[x][l]>k:\n",
    "                    l+=1\n",
    "                ans = max(ans,r-l+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], kk: int) -> int:\n",
    "        array = collections.defaultdict(list)\n",
    "        for i,v in enumerate(nums):\n",
    "            array[v].append(i)\n",
    "        print(array)\n",
    "        res = 1\n",
    "        for k,v in array.items():\n",
    "            n = len(v)\n",
    "            if n <= 1:\n",
    "                continue \n",
    "            left,right = 0,1\n",
    "            while right < n :\n",
    "                cur = right -left +1 \n",
    "                length = v[right]-v[left] + 1 \n",
    "                diff = length - cur \n",
    "                # print(left,right,cur,length,diff)\n",
    "                if diff <= kk :\n",
    "                    res = max(res,cur)\n",
    "                if diff <= kk :\n",
    "                    right += 1 \n",
    "                else:\n",
    "                    left += 1 \n",
    "            # print(\"_______________\")\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums_dict = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            nums_dict[num].append(i)\n",
    "\n",
    "        print(nums_dict)\n",
    "        ans = 0\n",
    "        for item in nums_dict.values():\n",
    "            if len(item) <= ans: continue\n",
    "            left = 0\n",
    "            for right, p_num in enumerate(item):\n",
    "                while p_num - item[left] - (right - left) > k:\n",
    "                    left += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 将每一个数归位一类，然后在每一个数上面进行双指针\n",
    "        dic = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            dic[x].append(i)\n",
    "        print(dic)\n",
    "        ans = 1\n",
    "        for i, arr in dic.items():\n",
    "            # print(i, arr)\n",
    "            m = len(arr)\n",
    "            if m == 1: continue\n",
    "            left = 0\n",
    "            mx = 0\n",
    "            tot = k\n",
    "            for j in range(1, m):\n",
    "                while tot < arr[j] - arr[j-1] - 1:\n",
    "                    left += 1\n",
    "                    tot += arr[left] - arr[left-1] - 1\n",
    "                tot -= arr[j] - arr[j-1] - 1\n",
    "                mx = max(mx, j - left + 1)\n",
    "            ans = max(mx, ans)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        res = left = 0\n",
    "        mapv = {v:index + 1 for index, v in enumerate(set(nums))}\n",
    "        maxLen = len(mapv)\n",
    "\n",
    "        st = [0] * (4 * maxLen + 1)\n",
    "        def update(index, val, node = 1, left = 0, right= maxLen):\n",
    "            if index < left or index > right: return\n",
    "            if left == right and index == left:\n",
    "                st[node] += val\n",
    "                return \n",
    "            mid = left + right >> 1\n",
    "            update(index, val, node * 2, left, mid)\n",
    "            update(index, val, node * 2 + 1, mid + 1, right)\n",
    "            st[node] = st[node * 2] if st[node * 2] > st[node * 2 + 1] else st[node * 2 + 1]\n",
    "\n",
    "        for right, item in enumerate(nums):\n",
    "            update(mapv[item], 1)\n",
    "            while ((right - left + 1) - st[1]) > k:\n",
    "                update(mapv[nums[left]], -1)\n",
    "                left += 1\n",
    "            res = max(res, st[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        res = left = 0\n",
    "        mapv = {v:index + 1 for index, v in enumerate(set(nums))}\n",
    "        maxLen = len(mapv)\n",
    "\n",
    "        st = [0] * (4 * maxLen + 1)\n",
    "        def update(index, val, node = 1, left = 0, right= maxLen):\n",
    "            if index < left or index > right: return\n",
    "            if left == right and index == left:\n",
    "                st[node] += val\n",
    "                return \n",
    "            mid = left + right >> 1\n",
    "            if mid >= left:\n",
    "                update(index, val, node * 2, left, mid)\n",
    "            if mid <= right:\n",
    "                update(index, val, node * 2 + 1, mid + 1, right)\n",
    "            st[node] = st[node * 2] if st[node * 2] > st[node * 2 + 1] else st[node * 2 + 1]\n",
    "\n",
    "        for right, item in enumerate(nums):\n",
    "            update(mapv[item], 1)\n",
    "            while ((right - left + 1) - st[1]) > k:\n",
    "                update(mapv[nums[left]], -1)\n",
    "                left += 1\n",
    "            res = max(res, st[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        counter = Counter(nums)\n",
    "        pos = [[] for _ in range(len(nums) + 1)]\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i - len(pos[x]))\n",
    "        ans = 0\n",
    "        for ps in pos:\n",
    "            if len(ps) <= ans: continue\n",
    "            left = 0\n",
    "            for right, p in enumerate(ps):\n",
    "                while p - ps[left] > k:  \n",
    "                    left += 1\n",
    "                ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        def check(length):\n",
    "            for value in d.values():\n",
    "                for i in range(len(value) - length + 1):\n",
    "                    if value[i] + k + length - 1 >= value[i+length-1]:\n",
    "                        return True\n",
    "            return False\n",
    "                # if len(value) < length:\n",
    "                    \n",
    "        d = dict()\n",
    "        for step, n in enumerate(nums):\n",
    "            if n not in d:\n",
    "                d[n] = []\n",
    "            d[n].append(step)\n",
    "            \n",
    "        # print(d)\n",
    "            \n",
    "        maxAns = max(Counter(nums).values())\n",
    "        \n",
    "        l, r = 1, maxAns\n",
    "        while r - l > 1:\n",
    "            mid = (r + l) >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "                \n",
    "        if check(r):\n",
    "            return r\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        \n",
    "        def dfs(list1,k):\n",
    "            a = 0\n",
    "            left,right = 0,0\n",
    "            while right<len(list1) and left<=right:\n",
    "                while right<len(list1)  and k>=0:\n",
    "                    k -= list1[right]\n",
    "                    right +=1\n",
    "                if k<0:\n",
    "                    a = max(a,right-left-1)\n",
    "                else:\n",
    "                    a = max(a,right-left)\n",
    "                while left<right and k<0:\n",
    "                    k+=list1[left]\n",
    "                    left+=1\n",
    "            return a+1\n",
    "                \n",
    "        temp = {}\n",
    "        temp_1 ={}\n",
    "        for i,num in enumerate(nums):\n",
    "            if num not in temp:\n",
    "                temp[num] = []\n",
    "                temp_1[num] = i\n",
    "            else:\n",
    "                temp[num].append(i-temp_1[num]-1)\n",
    "                temp_1[num]=i\n",
    "        ans = 0\n",
    "        for v in temp.values():\n",
    "            a = dfs(v,k)\n",
    "            ans = max(ans,a)\n",
    "        return ans\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        h = [] # 窗口内最多字符\n",
    "        cnt = Counter()\n",
    "        # win 元素数量\n",
    "        # [l, r] \n",
    "        # 最长等值子数组长度: win 内最少的\n",
    "        n = len(nums)\n",
    "        ans = j = 0\n",
    "        for i, c in enumerate(nums):\n",
    "            cnt[c] += 1\n",
    "            heappush(h, (-cnt[c], c))\n",
    "            while j <= i and i - j + 1 + h[0][0] > k:\n",
    "                x = nums[j]\n",
    "                cnt[x] -= 1\n",
    "                if x == h[0][-1]:\n",
    "                    heapreplace(h, (h[0][0]+1, x))\n",
    "                else:\n",
    "                    heappush(h, (-cnt[x], x))\n",
    "                j += 1\n",
    "            ans = max(ans, -h[0][0])\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        res = left = 0\n",
    "        mapv = {v:index + 1 for index, v in enumerate(sorted(set(nums)))}\n",
    "        maxLen = len(mapv)\n",
    "\n",
    "        st = [0] * (4 * maxLen + 1)\n",
    "        def update(index, val, node = 1, left = 0, right= maxLen):\n",
    "            if index < left or index > right: return\n",
    "            if left == right and index == left:\n",
    "                st[node] += val\n",
    "                return \n",
    "            mid = left + right >> 1\n",
    "            update(index, val, node * 2, left, mid)\n",
    "            update(index, val, node * 2 + 1, mid + 1, right)\n",
    "            st[node] = max(st[node * 2], st[node * 2 + 1])\n",
    "\n",
    "        for right, item in enumerate(nums):\n",
    "            update(mapv[item], 1)\n",
    "            while ((right - left + 1) - st[1]) > k:\n",
    "                update(mapv[nums[left]], -1)\n",
    "                left += 1\n",
    "            res = max(res, st[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l,r = 0,0\n",
    "        \n",
    "        cnt = Counter()\n",
    "        # 次数最大堆\n",
    "        heap = []\n",
    "        \n",
    "        res = 0\n",
    "        while r < n:\n",
    "            cnt[nums[r]] += 1\n",
    "            heappush(heap,(-cnt[nums[r]],nums[r]))\n",
    "            \n",
    "            r += 1\n",
    "            # 不满足题意，移动l指针\n",
    "            while r - l + heap[0][0] > k:\n",
    "                cnt[nums[l]] -= 1\n",
    "                \n",
    "                # lazy 删除，更新次数最大堆堆顶\n",
    "                heappush(heap,(-cnt[nums[l]],nums[l]))\n",
    "                while heap and cnt[heap[0][1]] != -heap[0][0]:\n",
    "                    heappop(heap)\n",
    "                \n",
    "                l += 1\n",
    "                \n",
    "            res = max(res,-heap[0][0])\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        res = left = 0\n",
    "        mapv = {v:index + 1 for index, v in enumerate(sorted(set(nums)))}\n",
    "        maxLen = len(mapv)\n",
    "\n",
    "        st = [0] * (4 * maxLen + 1)\n",
    "        def update(index, val, node = 1, left = 0, right= maxLen):\n",
    "            if index < left or index > right: return\n",
    "            if left == right and index == left:\n",
    "                st[node] += val\n",
    "                return \n",
    "            mid = left + right >> 1\n",
    "            update(index, val, node * 2, left, mid)\n",
    "            update(index, val, node * 2 + 1, mid + 1, right)\n",
    "            st[node] = st[node * 2] if st[node * 2] > st[node * 2 + 1] else st[node * 2 + 1]\n",
    "\n",
    "        for right, item in enumerate(nums):\n",
    "            update(mapv[item], 1)\n",
    "            while ((right - left + 1) - st[1]) > k:\n",
    "                update(mapv[nums[left]], -1)\n",
    "                left += 1\n",
    "            res = max(res, st[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longest_subarray_sum_less_than_k(self, nums, k):\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        left = 0\n",
    "        max_length = 0\n",
    "        current_sum = 0\n",
    "\n",
    "        for right in range(len(nums)):\n",
    "            current_sum += nums[right]\n",
    "\n",
    "            while current_sum > k:\n",
    "                current_sum -= nums[left]\n",
    "                left += 1\n",
    "\n",
    "            max_length = max(max_length, right - left + 1)\n",
    "\n",
    "        return max_length\n",
    "\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        mapping = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if mapping.get(num, None) == None:\n",
    "                mapping[num] = [i, []]\n",
    "            else:\n",
    "                last = mapping[num][0]\n",
    "                mapping[num][1].append(i - last - 1)\n",
    "                mapping[num][0] = i\n",
    "\n",
    "        for key, val in mapping.items():\n",
    "            _, pos = val\n",
    "            res = self.longest_subarray_sum_less_than_k(pos, k) + 1\n",
    "            ans = max(res, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        counts = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in counts:\n",
    "                last_i, cnt, i_diff_lst = counts[nums[i]]\n",
    "                counts[nums[i]][0] = i\n",
    "                counts[nums[i]][1] = cnt + 1\n",
    "                i_diff_lst.append(i - last_i - 1)\n",
    "            else:\n",
    "                counts[nums[i]] = [i, 1, []]\n",
    "        ans = 0\n",
    "        for x in counts:\n",
    "            _, cnt, i_diff_lst = counts[x]\n",
    "            if len(i_diff_lst) == 0: \n",
    "                ans = max(ans, 1)\n",
    "                continue\n",
    "            i, j = 0, 0\n",
    "            sums = 0\n",
    "            while j < len(i_diff_lst):\n",
    "                sums += i_diff_lst[j]\n",
    "                while sums > k:\n",
    "                    sums -= i_diff_lst[i]\n",
    "                    i += 1\n",
    "                j += 1\n",
    "                ans = max(ans, j-i+1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        q = defaultdict(list)\n",
    "        used = defaultdict(int)\n",
    "        res = 0\n",
    "        \n",
    "        for i,num in enumerate(nums) :\n",
    "            q[num].append(i)\n",
    "            if len(q[num]) > 1 :\n",
    "                delete = i - q[num][-2] - 1    \n",
    "                used[num] += delete\n",
    "            while used[num] > k and len(q[num]) > 1 :\n",
    "                first,second = q[num][0],q[num][1]\n",
    "                used[num] -= (second - first - 1)\n",
    "                q[num] = q[num][1:]\n",
    "            res = max(res, len(q[num]))\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        vals = {}\n",
    "        for idx,val in enumerate(nums):\n",
    "            if val not in vals: vals[val] = []\n",
    "            vals[val].append(idx)\n",
    "        \n",
    "        class A:\n",
    "            def __getitem__(self,res):\n",
    "                for ll in vals.values():\n",
    "                    if len(ll)<res:\n",
    "                        continue\n",
    "                    for i in range(len(ll)-res+1):\n",
    "                        i2 = i+res-1\n",
    "                        idx1,idx2 = ll[i],ll[i2]\n",
    "                        if idx2-idx1+1-res<=k:\n",
    "                            return 0\n",
    "                return 1\n",
    "        return bisect_left(A(),1,1,len(nums)+1)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        stat = [[] for _ in range(n+2)]\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            start,x = i,nums[i]\n",
    "            cnt = 1\n",
    "            i += 1\n",
    "            while i < n and nums[i] == nums[i-1]: \n",
    "                i += 1\n",
    "                cnt += 1\n",
    "            if len(stat[x]) == 0: stat[x].append((cnt, i, 0))\n",
    "            else: \n",
    "                skip = start - stat[x][-1][1]\n",
    "                stat[x].append((cnt, i, skip))\n",
    "        ans = 0\n",
    "        for x in stat:\n",
    "            i,j = 0,0\n",
    "            ss,tmp = 0,0\n",
    "            while i < len(x) and j < len(x):\n",
    "                if x[j][2] + ss <= k:\n",
    "                    ss += x[j][2]\n",
    "                    tmp += x[j][0]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    tmp -= x[i][0]\n",
    "                    i += 1\n",
    "                    if i < len(x): ss -= x[i][2]\n",
    "                ans = max(ans, tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 6467.找出最长等值子数组\n",
    "# https://leetcode.cn/problems/find-the-longest-equal-subarray/description/\n",
    "# lang=python\n",
    "\n",
    "\n",
    "# 解法: 双端队列\n",
    "from collections import defaultdict, deque\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        cost = [0] * len(nums)\n",
    "        v2i = {}\n",
    "        gs = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x not in v2i:\n",
    "                v2i[x] = i - 1\n",
    "            cost[i] = i - v2i[x] - 1\n",
    "            v2i[x] = i\n",
    "            gs[x].append(i)\n",
    "        \n",
    "        ans = 1\n",
    "        for g in gs.values():\n",
    "            if len(g) <= ans:\n",
    "                continue\n",
    "            q = deque()\n",
    "            c = 0\n",
    "            for i in g:\n",
    "                q.append(i)\n",
    "                c += cost[i]\n",
    "                while c > k:\n",
    "                    q.popleft()\n",
    "                    j = q[0]\n",
    "                    c -= cost[j]\n",
    "                ans = max(ans, len(q))\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    import time\n",
    "    \n",
    "    t0 = time.time()\n",
    "    \n",
    "    s = Solution()\n",
    "    func_name = dir(s)[-1]\n",
    "    func = getattr(s, func_name)\n",
    "    \n",
    "    print(func(nums=[1, 3, 2, 3, 1, 3], k=3))\n",
    "    # 输出：3\n",
    "    print(func(nums=[1, 1, 2, 2, 1, 1], k=2))\n",
    "    # 输出：4\n",
    "    \n",
    "    t1 = time.time()\n",
    "    print(t1 - t0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        len_d = defaultdict(list)\n",
    "        interval_d = defaultdict(list)\n",
    "        last_idx_d = defaultdict(int)\n",
    "\n",
    "        total_length = 0\n",
    "        for x, it in groupby(nums):\n",
    "            length = len(list(it))\n",
    "            len_d[x].append(length)\n",
    "            if len(len_d[x]) > 1:\n",
    "                interval_d[x].append(total_length - last_idx_d[x])\n",
    "            total_length += length\n",
    "            last_idx_d[x] = total_length\n",
    "\n",
    "        ans = 0\n",
    "        for x in len_d:\n",
    "            if x not in interval_d:\n",
    "                ans = max(ans, max(len_d[x]))\n",
    "            else:\n",
    "                interval_list = interval_d[x]\n",
    "                len_list = len_d[x]\n",
    "                s = len_list[0]\n",
    "                ans = max(ans, s)\n",
    "                interval_s = 0\n",
    "                i = 0\n",
    "                for j, interval in enumerate(interval_list):\n",
    "                    interval_s += interval\n",
    "                    s += len_list[j + 1]\n",
    "                    while interval_s > k:\n",
    "                        interval_s -= interval_list[i]\n",
    "                        s -= len_list[i]\n",
    "                        i += 1\n",
    "                    ans = max(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        intervals = [[] for _ in range(n + 1)]\n",
    "        \n",
    "        i = 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j + 1 < n and nums[j + 1] == nums[i]:\n",
    "                j += 1\n",
    "            intervals[nums[i]].append([i, j])\n",
    "            i = j + 1\n",
    "        \n",
    "        ans = 1\n",
    "        for num in range(1, n + 1):\n",
    "            interval = intervals[num]\n",
    "            if not interval or interval[-1][1] - interval[0][0] + 1 <= ans:\n",
    "                continue\n",
    "\n",
    "            breaks = list(accumulate([0] + [interval[i][0] - interval[i - 1][1] - 1 for i in range(1, len(interval))]))\n",
    "\n",
    "            l = 0\n",
    "            for R in range(len(interval)):\n",
    "                while breaks[R] - breaks[l] > k:\n",
    "                    l += 1\n",
    "                ans = max(ans, interval[R][1] - interval[l][0] + 1 - breaks[R] + breaks[l])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        num_2_indices_dict = dict()\n",
    "        ans = 0\n",
    "        \n",
    "        def get_len(arr:list[tuple]) -> int:\n",
    "            #print(\"arr -\", arr)\n",
    "            last_index, last_cnt = arr[-1]\n",
    "            left,right = 0, len(arr) - 1\n",
    "            ans = 0\n",
    "            while left <= right:\n",
    "                middle = (left + right) // 2\n",
    "                if (last_index - arr[middle][0] + 1) - (last_cnt - arr[middle][1] + 1) <= k:\n",
    "                    ans = last_cnt - arr[middle][1] + 1\n",
    "                    right = middle - 1\n",
    "                else:\n",
    "                    left = middle + 1\n",
    "            return ans\n",
    "        \n",
    "        for i,num in enumerate(nums):\n",
    "            if num in num_2_indices_dict:\n",
    "                cnt = num_2_indices_dict[num][-1][1]\n",
    "                num_2_indices_dict[num].append((i, cnt + 1))\n",
    "            else:\n",
    "                num_2_indices_dict[num] = [(i, 1)]\n",
    "            ans = max(ans, get_len(num_2_indices_dict[num]))\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        pre = nums[0]\n",
    "        cnt = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if pre == nums[i]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                dic[pre].append((cnt, i - cnt))\n",
    "                pre = nums[i]\n",
    "                cnt = 1\n",
    "        dic[pre].append((cnt, len(nums) - cnt))\n",
    "        # print(dic)\n",
    "\n",
    "        ans = 0\n",
    "        for _, val in dic.items():\n",
    "            (left_cnt, left_index) = val[0]\n",
    "            ans = max(ans, left_cnt)\n",
    "            if len(val) < 2:\n",
    "                continue\n",
    "\n",
    "            left, right = 0, 1\n",
    "            pre_cnt = left_cnt\n",
    "            while right < len(val):\n",
    "                (right_cnt, right_index) = val[right]\n",
    "                if right_index - left_index - pre_cnt <= k:\n",
    "                    pre_cnt += right_cnt\n",
    "                    ans = max(ans, pre_cnt)\n",
    "                    right += 1\n",
    "                else:\n",
    "                    pre_cnt -= val[left][0]\n",
    "                    left += 1\n",
    "                    (left_cnt, left_index) = val[left]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:#分类合并\n",
    "        dc=defaultdict(list)\n",
    "        l=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]!=nums[l]:\n",
    "                dc[nums[l]].append([l,i])\n",
    "                l=i\n",
    "        dc[nums[l]].append([l,len(nums)])\n",
    "        n=len(nums)\n",
    "        res=1\n",
    "        # print(dc)\n",
    "        for x in dc:\n",
    "            i=dc[x]\n",
    "            res=max(res,i[0][1]-i[0][0],i[-1][1]-i[-1][0])#+k\n",
    "            delNum=0\n",
    "            r=1\n",
    "            for j in range(len(i)-1):\n",
    "                \n",
    "                while r<len(i) and delNum+i[r][0]-i[r-1][1]<=k:\n",
    "                    delNum+=i[r][0]-i[r-1][1]\n",
    "                    r+=1\n",
    "                # delNum=k-(sm+i[r][0]-i[r-1][1]) if r<len(i) else k-sm\n",
    "                res=max(res,i[r-1][1]-i[j][0]-delNum)\n",
    "                delNum-=i[j+1][0]-i[j][1]\n",
    "            if res>=n:break\n",
    "        return min(n,res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        map = collections.defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            map[num].append(i)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        # print(map)\n",
    "        for i in range(1, n+1):\n",
    "            if map[i]:\n",
    "                arr = map[i]\n",
    "                left = 0\n",
    "                for right, num in enumerate(arr):\n",
    "\n",
    "                    while arr[right] - arr[left] - (right - left) > k:\n",
    "                        left += 1\n",
    "                    ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        arr = [[] for _ in range(n + 1)]  # [e_idx + 1, length, diff, pre_sum]\n",
    "        ln, v = 0, 0\n",
    "        ans = 0\n",
    "\n",
    "        def update(i):\n",
    "            nonlocal ans\n",
    "            lst = [i - 1, 0, 0, 0] if not arr[v] else arr[v][-1]\n",
    "            diff = i - lst[0] - ln + lst[2]\n",
    "            sm = lst[3] + ln\n",
    "            arr[v].append([i, ln, diff, sm])\n",
    "            idx = bisect.bisect_left(arr[v], diff - k, key=lambda x: x[2])\n",
    "            pre_sum = arr[v][idx - 1][3] if idx > 0 else 0\n",
    "            return sm - pre_sum\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == v:\n",
    "                ln += 1\n",
    "            else:\n",
    "                ans = max(ans, update(i))\n",
    "                ln, v = 1, num\n",
    "        ans = max(ans, update(n))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestEqualSubarray(self, nums: List[int], k: int) -> int:\n",
    "        record={}\n",
    "        ans=0\n",
    "        if not nums:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            a=record.get(nums[i],[])\n",
    "            if a:\n",
    "                used=i-a[-1][0]-1+a[-1][2]\n",
    "                o=a[-1][1]+1\n",
    "            else:\n",
    "                used=0\n",
    "                o=1\n",
    "            a.append([i,o,used])\n",
    "            while used-a[0][2]>k:\n",
    "                a.pop(0)\n",
    "            temp=a[-1][1]-a[0][1]+1\n",
    "            ans=max(ans,temp)\n",
    "            record[nums[i]]=a\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
